package com.xiaolin.algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName ShellSort
 * @Description 希尔排序（缩小增量排序）,是插入排序的改进版
 * @Detail 如果按照图解的理解去编写代码，那么需要四层嵌套，但我们编写代码的时候，可以简化代码，使循环变成三层
 * @Author MyPC
 * @Date 2020/7/19
 * @Version 1.0
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr={8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
        //第一遍  3,5,1,6,0,8,9,4,7,2
        //第二遍  0,2,1,4,3,5,7,6,9,8
        //第三遍  0,1,2,3,4,5,6,7,8,9
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 从小到大排序
     * 此种方式是交换法
     * @param arr
     */
    public static void shellSort(int[] arr){
        int temp=0;
        //gap为步长
        for(int gap=arr.length/2;gap>=1;gap/=2){
            //group为组数，这里不以组数作为循环，不然要分成四层循环
            for(int group=gap;group<arr.length;group++){
                //这层循环，不具体分组分别去排序，而是所有组都一起排序，rel是组的元素，第一次取时是第一组的第二个元素
                //向前进行反向遍历进行排序，直到遍历到第一个元素
                for (int rel=group-gap;rel>=0;rel-=gap){
                    if(arr[rel] > arr[rel+gap]){
                        temp=arr[rel];
                        arr[rel]=arr[rel+gap];
                        arr[rel+gap]=temp;
                    }
                }
            }
        }
    }
}
